package Solutions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * 示例：
 * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 * </p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ThreeSum {
    /***
     * 三数之和
     * @param data 传入数组
     * @return 满足条件的所有解
     */
    public List<List<Integer>> threeSum(int[] data) {
        List<List<Integer>> res = new ArrayList<>();
        if (data == null || data.length <= 2) return res;// 当data为空或者长度小于3的时候，是不存在解的，直接返回空解
        Arrays.sort(data);// 排序数组，可以有效地去重
        System.out.println(Arrays.toString(data));
        for (int i = 0; i < data.length; i++) {// 选定target
            if (i > 0 && data[i] == data[i - 1]) {
                continue;// 如果不是初值且和之前的值一致，说明重复，该值跳过即可
            }
            int target = -data[i];
            // 左右指针
            int left = i + 1, right = data.length - 1;
            while (left < right) {
                if (data[left] + data[right] == target) {// 说明此时找到一个符合要求的解
                    List<Integer> tmp = new ArrayList<>();// 构造结果元素，添加到res中
                    tmp.add(data[i]);
                    tmp.add(data[left]);
                    tmp.add(data[right]);
                    res.add(tmp);
                    // 结果元素添加完成后，左右指针向中间移动一步
                    left++;
                    right--;
                    // 需要判断移动后指针对应的值是否是重复使用的，如果是就直接跳过，同时注意到边界值的限制
                    while (left < data.length - 1 && data[left] == data[left - 1]) left++;
                    while (right > i && data[right] == data[right + 1]) right--;
                } else if (data[left] + data[right] < target) {
                    // 当和比target小的时候，我们将左指针移动一步，使得最终得到的值逐步地靠近target
                    left++;
                } else {
                    // 同理，目的是为了逐步地靠近target值
                    right--;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] data = new int[]{-2, 0, 3, -1, 4, 0, 3, 4, 1, 1, 1, -3, -5, 4, 0};
        ThreeSum sol = new ThreeSum();
        System.out.println(sol.threeSum(data));
    }
}
